//#define _CRT_SECURE_NO_WARNINGS 1
//#pragma warning(disable:6031)
//
//#include<stdio.h>
//#include<stdlib.h>
//
//struct ListNode {
//    int val;
//    struct ListNode *next;
//    ListNode(int x) : val(x), next(NULL) {}
//};
//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x)
//    {
//        struct ListNode* guard;
//        struct ListNode* head = pHead;
//        struct ListNode* ret;
//        guard = (struct ListNode*)malloc(sizeof(struct ListNode));
//        ret = (struct ListNode*)malloc(sizeof(struct ListNode));
//        int flag = 1;
//        while (head->next)
//        {
//            if (head->val < x)
//            {
//                guard->next = head;
//                if (flag)
//                {
//                    ret->next = head;
//                }
//                flag = 0;
//            }
//            guard = guard->next;
//            head = head->next;
//        }
//        if (flag)
//        {
//            ret->next = head;
//        }
//        while (head->next)
//        {
//            if (head->val >= x)
//            {
//                guard->next = head;
//            }
//            guard = guard->next;
//            head = head->next;
//        }
//        return ret->next;
//    }
//};
//
//
//int main()
//{
//    Partition()
//    return 0;
//}
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x)
    {
        struct ListNode* lesshead, * lesstail, * greaterhead, * greatertail;
        lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur = pHead;
        while (cur)
        {
            if (cur->val < x)
            {
                lesstail->next = cur;
                lesstail = lesstail->next;
            }
            else
            {
                greatertail->next = cur;
                greatertail = greatertail->next;
            }
            cur = cur->next;
        }
        lesstail->next = greaterhead->next;
        greatertail->next = NULL;
        pHead = lesshead->next;

        return pHead;

    }
};